

/**
 * author: Vevi Zhong
 */
public class insertSort{
    /**
     * [sort description]:直接插入排序算法，
     * 分类：内部比较排序
     * 数据结构：数组
     * 最差时间复杂度：最坏情况是输入序列是降序排列的，此时时间复杂度是O(n^2)
     * 最优时间复杂度：最好情况是输入序列是升序排列的，此时时间复杂度为O(n)
     * 平均时间复杂度：O(n^2)
     * 所需辅助空间：O(1)
     * 稳定性：稳定
     * @param array [description]
     */
	public void sort(int [] array){
		int len = array.length;
		for (int i=1; i<len; i++) {//默认第一个数是排好序的，所以从第二个数开始
			int current = array[i];
			int j = i - 1;
			/**
			 * 在排好序的数组中，从右往左遍历，遇到比current小的数停止，表示找到current数的位置
			 */
			while(j >= 0 && array[j] > current){ 
				array[j+1] = array[j];
				j --;
			}
			array[j] = current;
		}
	}
}